package com.gushuang.leetcode;

import java.util.HashMap;
import java.util.Map;
//https://leetcode.cn/problems/minimum-window-substring
public class minimumWindowSubstring {
    public String minWindow(String s, String t) {
        // 如果 s 的长度小于 t 的长度，说明 s 不可能包含 t，直接返回空字符串
        if (s.length() < t.length()) return "";

        // 用于记录目标字符串 t 中各个字符的需求数量
        Map<Character, Integer> need = new HashMap<>();
        // 用于记录当前窗口中各个字符的数量
        Map<Character, Integer> window = new HashMap<>();

        // 初始化 need 映射，将 t 中的字符及其出现次数存入 need
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 定义两个指针 left 和 right 作为窗口的左右边界，初始时都指向字符串的开头
        int left = 0, right = 0;
        // 记录当前窗口中满足 need 要求的字符数量
        int valid = 0;
        // 记录最小覆盖子串的起始位置和长度，初始值为最大整数（意味着还没有找到有效的子串）
        int start = 0, minLen = Integer.MAX_VALUE;

        // 开始移动右指针，扩展窗口
        while (right < s.length()) {
            // 将当前右边界的字符加入窗口
            char c = s.charAt(right);
            right++;

            // 如果当前字符是目标字符串 t 中的字符，更新 window 中该字符的计数
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果窗口中该字符的数量达到目标数量，更新 valid 的值
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 当 valid 的值等于 need 的大小时，说明当前窗口已经覆盖了 t 中的所有字符
            while (valid == need.size()) {
                // 更新最小子串的长度和起始位置
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }

                // 准备收缩窗口，将左边界向右移动
                char d = s.charAt(left);
                left++;
                // 如果即将移除的字符是目标字符串 t 中的字符，更新 window 和 valid
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    // 移除窗口中该字符的计数
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        // 如果 minLen 未更新，说明没有符合条件的子串，返回空字符串
        // 否则返回最小覆盖子串
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

}
